// 执行用时为 116 ms 的范例

#include <stdio.h>
#include <stdbool.h> // true
/*
**declaration of classes:
*/
struct Node
{
  int index;
  int bignum;
  struct Node *next;
};

struct set
{
  struct Node **hashTable;
  int size;
  int modNum;
};
/*
**Node methods:
*/
void Node_init(struct Node *self, int index, int bignum)
{
  self->index = index;
  self->bignum = bignum;
  self->next = NULL;
}

struct Node *Node_insert(struct Node *self, struct Node *elem)
{
  elem->next = self;
  return elem;
}

void Node_del(struct Node *self)
{
  struct Node *cur_pointer = self;
  while (true)
  {
    if (!cur_pointer)
      break;
    struct Node *tmp_pointer = cur_pointer;
    cur_pointer = cur_pointer->next;
    free(tmp_pointer);
  }
}
/*
**set methods:
*/
void set_init(struct set *self, int modNum)
{
  self->hashTable = (struct Node **)malloc(sizeof(struct Node *) * modNum);
  int i;
  for (i = 0; i < modNum; i++)
  {
    self->hashTable[i] = NULL;
  }
  self->modNum = modNum;
  self->size = 0;
}
int set_hash(const struct set *self, int bignum)
{
  return (bignum % self->modNum + self->modNum) % self->modNum;
}
void set_insert(struct set *self, int index, int bignum)
{
  int hashnum = set_hash(self, bignum);
  struct Node *tmp = (struct Node *)malloc(sizeof(struct Node));
  Node_init(tmp, index, bignum);
  self->hashTable[hashnum] = Node_insert(self->hashTable[hashnum], tmp);
  self->size++;
}
int set_query(const struct set *self, int bignum)
{
  int hashnum = set_hash(self, bignum);
  struct Node *cur_pointer = self->hashTable[hashnum];
  while (true)
  {
    if (!cur_pointer)
      return -1;
    if (cur_pointer->bignum == bignum)
      return cur_pointer->index;
    cur_pointer = cur_pointer->next;
  }
}
void set_del(struct set *self)
{
  int i;
  for (i = 0; i < self->modNum; i++)
  {
    Node_del(self->hashTable[i]);
  }
  free(self->hashTable);
}
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int *twoSum(int *nums, int numsSize, int target, int *returnSize)
{
  struct set *numsSet = (struct set *)malloc(sizeof(struct set));
  set_init(numsSet, 997);
  int i;
  int *ret = (int *)malloc(sizeof(int) * 2);
  *returnSize = 0;
  for (i = 0; i < numsSize; i++)
  {
    set_insert(numsSet, i, nums[i]);
  }
  for (i = 0; i < numsSize; i++)
  {
    int result = set_query(numsSet, target - nums[i]);
    if (result != -1 && i != result)
    {
      *returnSize = 2;
      ret[0] = i < result ? i : result;
      ret[1] = i < result ? result : i;
      break;
    }
  }
  set_del(numsSet);
  free(numsSet);
  return ret;
}